home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / FROMUTS / UNIXLIB37B / src / c / qsort < prev    next >
Text File  |  1991-02-13  |  3KB  |  189 lines
  1. #ifdef __STDC__
  2. static char sccs_id[] = "@(#) qsort.c 2.3 "__DATE__" HJR";
  3. #else
  4. static char sccs_id[] = "@(#) qsort.c 2.3 26/9/90 HJR";
  5. #endif
  6.  
  7. /* qsort.c (c) Copyright 1990 H.Rogers */
  8.  
  9. #ifdef __STDC__
  10. #include <stddef.h>
  11. #include <stdlib.h>
  12. #else
  13. #include "sys/types.h"
  14. extern void qsort();
  15. #endif
  16. #include <string.h>
  17.  
  18. #define N_INSERT    8
  19.  
  20. static char *__t;
  21.  
  22. static size_t __z;
  23. #ifdef __STDC__
  24. static int (*__c)(const void *,const void *);
  25. #else
  26. static int (*__c)();
  27. #endif
  28.  
  29. /* fast insertion sort - used for n <= N_INSERT */
  30.  
  31. #ifdef __STDC__
  32. static void __isort(register char *b,register size_t n)
  33. #else
  34. static void __isort(b,n)
  35. register char *b;
  36. register size_t n;
  37. #endif
  38. {
  39. register size_t z = __z;
  40. #ifdef __STDC__
  41. register int (*c)(const void *,const void *) = __c;
  42. #else
  43. register int (*c)() = __c;
  44. #endif
  45. register char *m,*e,*p;
  46. register char *t;
  47.  
  48. #define swap(x,y) (memcpy(t,x,z),memcpy(x,y,z),memcpy(y,t,z))
  49. #define move(x,y,z) memmove(x,y,z)
  50. #define push(x) memcpy(t,x,z)
  51. #define pull(x) memcpy(x,t,z)
  52.  
  53. t = __t;
  54.  
  55. e = b + (n * z);        /* past end */
  56.  
  57. /* find minimum */
  58.  
  59. for (m = p = b; (p += z) < e; )
  60.   if ((*c)(m,p) > 0)
  61.     m = p;
  62.  
  63. /* swap minimum into base */
  64.  
  65. if (m != b) swap(m,b);
  66.  
  67. /* standard insertion sort */
  68.  
  69. for (m = b; (p = m += z) < e; )
  70.   {
  71.   while ((*c)(p -= z,m) > 0);
  72.   if ((p += z) != m)
  73.     push(m),move(p + z,p,m - p),pull(p);
  74.   }
  75.  
  76. #undef swap
  77. #undef move
  78. #undef push
  79. #undef pull
  80. }
  81.  
  82. /* quicksort - used for n > N_INSERT */
  83.  
  84. #ifdef __STDC__
  85. static void __qsort(register char *b,register size_t n)
  86. #else
  87. static void __qsort(b,n)
  88. register char *b;
  89. register size_t n;
  90. #endif
  91. {
  92. register size_t z = __z;
  93. #ifdef __STDC__
  94. register int (*c)(const void *,const void *) = __c;
  95. #else
  96. register int (*c)() = __c;
  97. #endif
  98. register char *m,*e,*p,*t;
  99. register int i,j,k;
  100.  
  101. #define swap(x,y) (memcpy(t,x,z),memcpy(x,y,z),memcpy(y,t,z))
  102.  
  103. loop:
  104.  
  105. t = __t;
  106.  
  107. m = b + ((n>>1) * z);          /* middle */
  108. e = b + ((n - 1) * z);          /* end */
  109.  
  110. /* find pivot - median of b,m,e */
  111.  
  112. if ((*c)(b,m) >= 0) p = b; else p = m,m = b;
  113. if ((*c)(p,e) > 0) p = ((*c)(m,e) >= 0) ? m : e;
  114.  
  115. /* swap pivot into base */
  116.  
  117. if (p != b) swap(p,b);
  118.  
  119. /* standard quicksort & check for flat partition */
  120.  
  121. m = b; i = 0; j = 1;
  122. for (p = b; (p += z) <= e; )
  123.   {
  124.   if (!(k = (*c)(p,b))) j++;
  125.   if (k < 0)
  126.     { if ((m += z) != p) swap(m,p); i++; }
  127.   }
  128.  
  129. if (j == n) return;    /* exit if flat */
  130.  
  131. if (b != m) swap(b,m);
  132.  
  133. m += z;
  134.  
  135. /* sort smallest partition first */
  136.  
  137. if (i < (n>>1))
  138.   {
  139.   if (i > N_INSERT)
  140.     __qsort(b,i);
  141.   else if (i > 1)
  142.     __isort(b,i);
  143.   i = n - i - 1;
  144.   }
  145. else
  146.   {
  147.   i = n - i - 1;
  148.   if (i > N_INSERT)
  149.     __qsort(m,i);
  150.   else if (i > 1)
  151.     __isort(m,i);
  152.   i = n - i - 1;
  153.   m = b;
  154.   }
  155.  
  156. if (i > N_INSERT)
  157.   { b = m; n = i; goto loop; }    /* iterate larger partition */
  158. else if (i > 1)
  159.   __isort(m,i);
  160.  
  161. #undef swap
  162. }
  163.  
  164. #ifdef __STDC__
  165. void qsort(register void *v,register size_t n,register size_t z,
  166.     register int (*c)(const void *,const void *))
  167. #else
  168. void qsort(v,n,z,c)
  169. register void *v;
  170. register size_t n;
  171. register size_t z;
  172. register int (*c)();
  173. #endif
  174. {
  175. if (n < 2) return;
  176.  
  177. if (!(__t = malloc(z))) return;
  178.  
  179. __z = z;
  180. __c = c;
  181.  
  182. if (n > N_INSERT)
  183.   __qsort((char *)v,n);
  184. else if (n > 1)
  185.   __isort((char *)v,n);
  186.  
  187. free(__t);
  188. }
  189.